Ethernet is rapidly becoming the protocol of choice for consumer, enterprise and carrier networks. It is expected that most networks will evolve such that Ethernet will be the technology used to transport all the multimedia applications including, for example, triple-play, Fixed-Mobile-Convergence (FMC), and IP multimedia sub-systems (IMS). Existing network elements which offer network access using Ethernet technology are not designed to make maximum use of the legacy network links existing at the edge of the carrier networks. The edge of the network is quickly becoming a bottleneck as the new applications are becoming more and more demanding for bandwidth.
Telecommunications carriers are constantly looking for new revenue sources. They need to be able to deploy rapidly a wide ranging variety of services and applications without the need to constantly modify the network infrastructure. Ethernet is a promising technology that is able to support a variety of application requiring different quality of service (QoS) from the network. The technology is now being standardized to offer different types of services which have different combinations of quality objectives, such as loss, delay and bandwidth. Bandwidth objectives are defined in terms Committed Information Rate (CIR) or Excess Information Rate (EIR). The CIR guarantees bandwidth to a connection while the EIR allows it to send at higher bandwidth when available.
In existing IP/MPLS networks, each switching element or node needs to be involved in determining the MPLS path, which requires a lot of processing power and software complexity and is operationally complex.
Most modern connection-oriented systems for packet networks use MPLS over IP networks, and connections are setup by signaling protocols such as RSVP-TE. These protocols use shortest-path algorithms combined with non-real-time information on available QoS and bandwidth resources. Each node needs to maintain forwarding tables based on control traffic sent in the network. The paths available can be constrained by pruning links not meeting the bandwidth requirements. Bandwidth is wasted because of control messaging to establish and update forwarding tables. Protocols such as OSPF, LDP and RSVP are required to set up such paths, and these control protocols consume overhead bandwidth proportional to the size of the network and the number of connections.
Pure Ethernet networks require spanning tree and broadcast messages to select a “path”. Packets are broadcast over the tree while reverse learning new MAC addresses. In heavily loaded networks this function uses a lot of bandwidth to find the correct paths. To properly engineer for QoS, this type of network requires ensuring the links not in the spanning tree are assumed to be fully utilized, thus wasting additional resources.
The complexity of both Ethernet and MPLS/IP networks also affects the ability to perform network troubleshooting which increases significantly the operational costs. Routing consists of two basic tasks:                Collect/maintain state information of the network.        Search this information for a feasible, possibly optimal path.        
Each link in the network is associated with multiple constraint parameters which can be classified into:                Additive: the total value of an additive constraint for an end-to-end path is given by the sum of the individual link constraint values along the path (e.g.: delay, jitter, cost).        Non-additive: the total value of a non-additive constraint for an end-to-end path is determined by the value of that constraint at the bottleneck link (e.g.: bandwidth).        
Non-additive constraints can be easily dealt with using a preprocessing step by pruning all links that do not satisfy these constraints. Multiple simultaneous additive constraints are more challenging.
QoS or constraint-based routing consists of identifying a feasible route that satisfies multiple constraints (e.g.: bandwidth, delay, jitter) while simultaneously achieving efficient utilization of network resources.
Multi-constrained path selection, with or without optimization, is an NP-complete problem (e.g., cannot be exactly solved in polynomial time) and therefore computationally complex and expensive. Heuristics and approximation algorithms with polynomial-time complexities are necessary to solve the problem.
Most commonly used are shortest-path algorithms which take into account a single constraint for path computation, such as hop-count or delay. Those routing algorithms are inadequate for multimedia applications (e.g., video or voice) which require multiple constraints to guarantee QoS, such as delay, jitter and loss.
Path computation algorithms for single-metric are well known; for example, Dijkstra's algorithm is efficient in finding the optimal path that maximizes or minimizes one single metric or constraint.
However, using a single primitive parameter such as delay is not sufficient to support the different types of services offered in the network.
Sometimes a single metric is derived from multiple constraints by combining them in a formula, such as:CC=BW/(D*J)where CC=composite constraint, BW=bandwidth, D=delay, and J=jitter. The single metric, a composite constraint, is a combination of various single constraints. In this case, a high value of the composite constraint is achieved if there is high available bandwidth, low delay and low jitter. The selected path based on the single composite constraint most likely does not simultaneously optimize all three individual constraints (maximum bandwidth, minimal delay and loss probability), and thus QoS may not be guaranteed. Any of the constraints by itself may not even satisfy the original path requirement.
To support QoS requirements, a more complex model of the network is required that takes into account all constraints such as bandwidth, delay, delay jitter, availability and loss probability. Multiple routing metrics greatly increase the complexity of path computation. New algorithms have to be found that can compute paths that satisfy multiple constraints in practical elapsed time.
Algorithms such as spanning trees are used to prevent loops in the data path in Ethernet networks because of their connectionless nature and the absence of a Time-To-Live (TTL) attribute, which can create infinite paths Such algorithms proactively remove links from being considered in a path in order to prevent loops. This artifact of the connectionless routing scheme is costly as it prevents the use of expensive links, which remain underutilized.
On top of the above issues, business policies, such as overbooking per QoS, are ignored by the algorithms establishing the paths. These business policies are important to controlling the cost of network operations. Because of these complexity issues, it is difficult for a carrier to deploy cost-efficiently QoS-based services in the metropolitan and access networks where bandwidth resources are restricted. In the core networks, where more bandwidth is available, the bandwidth is over-engineered to ensure that all the QoS objectives can be met.
With an offline traffic engineering system, the state of all existing connection requests and the utilization of all network links are known before the new requested paths are computed. Using topology information, such as link capacities and a traffic demand matrix, a centralized server performs global optimization algorithms to determine the path for each connection request. Once a path design is completed, the connections are generally set up by a network management system. It is well known that an offline system with global optimization can achieve considerable improvement in resource utilization over an online system, if the traffic matrix accurately reflects the current load the network is carrying.
Existing traffic engineering systems do not keep in sync with the actual network or maintain real-time information on the bandwidth consumed while the network changes due to link failures, variations in the traffic generated by the applications, and unplanned link changes. The existing traffic engineering systems also do not take into account business policies such as limiting how much high priority traffic is going on a link.